package BinomialHeap;


import java.util.HashSet;

public class BinomialHeap /*implements java.io.Serializable*/ {

    // internal class BinomialHeapNode
    public static class BinomialHeapNode /*implements java.io.Serializable*/ {
    //private static final long serialVersionUID=6495900899527469811L;

    //private int key;                      // element in current node
    private Integer key;                      // element in current node
    private int degree;                   // depth of the binomial tree having the current node as its root
    private BinomialHeapNode parent;      // pointer to the parent of the current node
    private BinomialHeapNode sibling;     // pointer to the next binomial tree in the list
    private BinomialHeapNode child;       // pointer to the first child of the current node
    
    /*
    public BinomialHeapNode() {
        this(new Integer(0));
    }
    */

    //public BinomialHeapNode(int k) {
    public BinomialHeapNode(Integer k) {
        key = k;
        degree = 0;
        parent = null;
        sibling = null;
        child = null;
    }

      //public int getKey() {                     // returns the element in the current node
    public Integer getKey() {                     // returns the element in the current node
          return key;
      }
    
      //private void setKey(int value) {          // sets the element in the current node
    private void setKey(Integer value) {          // sets the element in the current node
          key = value;
      }
    
      public int getDegree() {                  // returns the degree of the current node
          return degree;
      }
    
      private void setDegree(int deg) {         // sets the degree of the current node
          degree = deg;
      }
    
      public BinomialHeapNode getParent() {     // returns the father of the current node
          return parent;
     }
    
      private void setParent(BinomialHeapNode par) {          // sets the father of the current node
          parent = par;
      }
    
      public BinomialHeapNode getSibling() {                  // returns the next binomial tree in the list
          return sibling;
      }
    
      private void setSibling(BinomialHeapNode nextBr) {      // sets the next binomial tree in the list
          sibling = nextBr;
      }
    
      public BinomialHeapNode getChild() {                    // returns the first child of the current node
          return child;
      }
    
      private void setChild(BinomialHeapNode firstCh) {       // sets the first child of the current node
          child = firstCh;
      }
    
    public int getSize() {
        return (1 + ((child == null)?0:child.getSize()) + ((sibling == null)?0:sibling.getSize()));
    }

    private BinomialHeapNode reverse(BinomialHeapNode sibl) {
        BinomialHeapNode ret;
        if (sibling != null) ret = sibling.reverse(this);
        else ret = this;
        sibling = sibl;
        return ret;
    }

 
    private BinomialHeapNode findMinNode() {
        BinomialHeapNode x = this, y = this;
        //int min = x.key;
        Integer min = x.key;
        
        while (x != null) {
        //if (x.key < min) {
        if (x.key.compareTo(min) < 0) {
            y = x;
            min = x.key;
        }
        x = x.sibling;
        }
        
        return y;
    }
    
    // Find a node with the given key
    //private BinomialHeapNode findANodeWithKey(int value) {
    private BinomialHeapNode findANodeWithKey(Integer value) {
        BinomialHeapNode temp = this, node = null;
        while (temp != null) {
        //if (temp.key == value) {
        if (temp.key.compareTo(value) == 0) {
            node = temp;
            break;
        }
        if (temp.child == null) temp = temp.sibling;
        else {
            node = temp.child.findANodeWithKey(value);
            if (node == null) temp = temp.sibling;
            else break;
        }
        }
        
        return node;
    }

    }
    
    // end of helper class BinomialHeapNode

    private BinomialHeapNode Nodes;
    private int size;

    public BinomialHeap() {
    Nodes = null;
    size = 0;
    }

  
    // 2. Find the minimum key
    //public int findMinimum() {
    private Integer findMinimum() {
    return Nodes.findMinNode().key;
    }

    // 3. Unite two binomial heaps
    // helper procedure
    private void merge(BinomialHeapNode binHeap) {
    BinomialHeapNode temp1 = Nodes, temp2 = binHeap;
    while ((temp1 != null) && (temp2 != null)) {
        if (temp1.degree == temp2.degree) {
        BinomialHeapNode tmp = temp2;
        temp2 = temp2.sibling;
        tmp.sibling = temp1.sibling;
        temp1.sibling = tmp;
        temp1 = tmp.sibling;
        }
        else {
        if (temp1.degree < temp2.degree) {
            if ((temp1.sibling == null) || (temp1.sibling.degree > temp2.degree)) {
            BinomialHeapNode tmp = temp2;
            temp2 = temp2.sibling;
            tmp.sibling = temp1.sibling;
            temp1.sibling = tmp;
            temp1 = tmp.sibling;
            }
            else temp1 = temp1.sibling;
        }
        else {
            BinomialHeapNode tmp = temp1;
            temp1 = temp2;
            temp2 = temp2.sibling;
            temp1.sibling = tmp;
            if (tmp == Nodes) Nodes = temp1;
        }
        }
    }
    
    if (temp1 == null) {
          temp1 = Nodes;
          while (temp1.sibling != null) temp1 = temp1.sibling;
          temp1.sibling = temp2;
      }
    }
    
    // another helper procedure
    private void unionNodes(BinomialHeapNode binHeap) {
    merge(binHeap);

    BinomialHeapNode prevTemp = null, temp = Nodes, nextTemp = Nodes.sibling;
    
    while (nextTemp != null) {
        if ((temp.degree != nextTemp.degree) || ((nextTemp.sibling != null) &&
                             (nextTemp.sibling.degree == temp.degree))) {
        prevTemp = temp;
        temp = nextTemp;
        }
        else {
        //if (temp.key <= nextTemp.key) {
        if (temp.key.compareTo(nextTemp.key) <=0) {
            temp.sibling = nextTemp.sibling;
            nextTemp.parent = temp;
            nextTemp.sibling = temp.child;
            temp.child = nextTemp;
            temp.degree++;
        }
        else {
            if (prevTemp == null) Nodes = nextTemp;
            else prevTemp.sibling = nextTemp;
            temp.parent = nextTemp;
            temp.sibling = nextTemp.child;
            nextTemp.child = temp;
            nextTemp.degree++;
            temp = nextTemp;
        }
        }
        
        nextTemp = temp.sibling;
    }
    }
    
 
    // 4. Insert a node with a specific value
    //public void insert(int value) {
    public void insert(Integer value) {
    //if (value > 0) {
    if (value.compareTo(new Integer(0)) > 0) {
        BinomialHeapNode temp = new BinomialHeapNode(value);
        if (Nodes == null) {
        Nodes = temp;
        size = 1;
        }
        else {
        unionNodes(temp);
        size++;
        }
    }
    }
    
    // 5. Extract the node with the minimum key
    //public int extractMin() {
    public Integer extractMin() {
    if (Nodes == null) return new Integer(-1);

    BinomialHeapNode temp = Nodes, prevTemp = null;
    BinomialHeapNode minNode = Nodes.findMinNode();
    //while (temp.key != minNode.key) {
    while (temp.key.compareTo(minNode.key) != 0) {
        prevTemp = temp;
        temp = temp.sibling;
    }
    
    if (prevTemp == null) Nodes = temp.sibling;
    else prevTemp.sibling = temp.sibling;
    temp = temp.child;
    BinomialHeapNode fakeNode = temp;
    while (temp != null) {
        temp.parent = null;
        temp = temp.sibling;
    }

    if ((Nodes == null) && (fakeNode == null)) size = 0;
    else {
        if ((Nodes == null) && (fakeNode != null)) {
        Nodes = fakeNode.reverse(null);
        size = Nodes.getSize();
        }
        else {
        if ((Nodes != null) && (fakeNode == null)) size = Nodes.getSize();
        else {
            unionNodes(fakeNode.reverse(null));
            size = Nodes.getSize();
        }
        }
    }

    return minNode.key;
    }

    // 6. Decrease a key value
    //public void decreaseKeyValue(int old_value, int new_value) {
    private void decreaseKeyValue(Integer old_value, Integer new_value) {
    BinomialHeapNode temp = Nodes.findANodeWithKey(old_value);
    temp.key = new_value;
    BinomialHeapNode tempParent = temp.parent;
    
    //while ((tempParent != null) && (temp.key < tempParent.key)) {
    while ((tempParent != null) && (temp.key.compareTo(tempParent.key) < 0)) {
        Integer z = temp.key;
        temp.key = tempParent.key;
        tempParent.key = z;
        
        temp = tempParent;
        tempParent = tempParent.parent;
    }
    }

    // 7. Delete a node with a certain key
    //public void delete(int value) {
    public void delete(Integer value) {
    if ((Nodes != null) && (Nodes.findANodeWithKey(value) != null)) {
        decreaseKeyValue(value, new Integer(findMinimum().intValue() - 1));
        extractMin();
    }
    }


 
}
// end of class BinomialHeap